The invention relates to a new method and system for retrieving stored graph representations according to a specified representation preference order. More specifically, it relates to retrieval of stored graph representations according to a procedure which seeks to select one of the available representations of an identified graph according to a representation level in a priority schedule of representation levels.
The invention operates in the environment of a general purpose computer connected through a communications system including plural communication channels that provide data interchange capability between the computer and a plurality of user terminals and a plurality of output devices. A user terminal is understood to refer to a typical terminal device including a keyboard, a display, and a limited computation facility, possibly together with one or more graphical output devices. Since a terminal normally includes a CRT having the capability to provide a visual output, terminal CRT's are included in the category of devices referred to as output devices.
In this document, a "graph" is any kind of pictorial representation including one or more symbols. As is known, graphs include but are not limited to: line charts, area charts, scattergrams, horizontal and vertical bar charts, pie charts, maps, tables, text pages, and other text displays, lists, and symbol diagrams, and combinations of these. A graphical output device is a computer controlled device capable of producing a visual image of a graph.
Existing graphics application programs, together with other prior art computer programs, are available to operate on the computer to create graphs in response to commands, parameters, and data received from users through the terminals communicatively connected to the computer or retrieved from data files or databases. Created graphs are dispatched by transmission of graphical data from the computer to the output devices. A graph is output when a visual representation of its image is produced either on a screen or a hardcopy medium such as paper or photographic slide material at an output device.
Typically, in the posited multi-user scenario, a number of terminals share the computer, using it simultaneously to do different things with it. In the situation of interest, the system is employed for the creation of graphs for end users. End use of a graph can involve the satisfaction of a plethora of user needs; for example, different users may retrieve a graph for viewing, printing, or alteration.
As is known, the levels of representation of a graph, also called levels of abstraction, correspond generally to the position between human understandability and machine understandability occupied by the expression of the graph. Thus, at the highest level of abstraction, graphs are represented by human language descriptions. At the lowest level of abstraction, the graph is expressed in a machine-language format that can be comprehended only by the device upon which the graph is to be produced. At an intermediate level graphs can be represented by a string of graphics primitives consisting of straightforward figure elements such as lines, polygons, circles, ellipses, circle segments, text, and filled polygons. Such strings also include graphics attributes which further modify the graphics primitives. The attributes include location coordinates, size, color, and typeface. The highest expression of a graph in human understandable form is referred to as a source file; an intermediate level representation is termed a metafile; while the lowest level of abstraction is a device specific file. It is to be understood that the term "metafile" is an accepted label for a particular kind of intermediate level expression. Other expressions, at different levels of abstraction than metafile, may also exist between source and device-specific files.
Characteristically, once a graph is created it will be expressed in one or more levels of abstraction in order to support certain functions. Functions are human initiated machine performances of particular work on a graph to achieve a definite purpose. For the purposes of this application, it is understood that processes exist which translate the expression of a graphical image at one level to an equivalent expression at a lower level.
As is known, the different uses to which a graph is put require that the machine understandable image representation of the graph be available at differing levels of machine abstraction. For example, in text processing the terms "final form" and "revisable form" are used to indicate two different levels of abstraction, each particularly designed for a specific function: the final form is that to be printed or viewed only, the revisable form is intended to be changed prior to printing. In graphics, there are more than just these two levels: the graph representation corresponding to the final form of text may be more or less tailored to the output processor of a certain graphical output device; and the revisable form, having a representation in a higher level of abstraction than the final form, may allow different kinds of revision to the graph.
The different kinds of graph representations imply different performance requirements for the centrally-operated graphical production system. Some representations provide cheap retrieval of a graph but limited flexibility in terms of choice of output device or modification. Other representations are flexible in terms of being adaptable to a variety of output devices, however, their maintenance, retrieval, and translation usually entail a high cost.
An archival problem in a centrally organized graphic system is characterized by the interplay of desired function and graphical representations. For example, retrieval of a graph image from storage for viewing on a CRT is most quickly accomplished and requires the least amount of computer processing if the graph is stored in the lowest level representation possible. For a CRT this would consist of the actual bit map of the graph's image or a device instruction stream convertible to a bit map. The bit map or instruction stream is easily retrieved from storage and formatted for transmission through a communications channel to the output device by conversion to a bit or byte sequence that is transmitted through the communications channel to the output device. This lowest-level representation requires no computer processing of the stored information but only transmission of the data to the graphics device.
Any higher level of representation, such as metafile format, would require additional processing for translation of the metafile to the bit map or instruction stream required by the device. However, if all graphs were represented in their lowest level of abstraction, the variety of output devices would proliferate the device specific files, since different output devices require different information. Therefore, support of several different output devices with a single device specific representation would not be possible. As the output device configurations multiply, so do the device specific representations of each graph. As the number of representations grows and is multiplied by the number of graphs, one can appreciate that the storage requirements of the centrally organized system increase correspondingly. Moreover, system operating costs are increased because of the processing cost of creating all of the files, and because of the administrative difficulty in keeping the different representations coordinated.
From the user standpoint, another disadvantage of device specific file storage is that the low level expression of a graph is very difficult to modify. Modification of a graph at this level of representation requires access to the graph figure elements, which are nothing more than patterns of bits in the device data stream. Therefore, a user would naturally seek a higher level of graph representation for purposes of modification.
Storage of graphs in representations at a higher level than device-specific (such as metafiles) requires processing of the representations to translate the representations to lower-level expressions. This processing increases the cost of sending the graph to an output device, but has the fundamental advantage that one representation is sufficient to handle a great number of devices.
However, metafile storage also has disadvantages. Storage of graphs in the form of metafiles brings diminishing reward if the ambition of a system is to support all different classes of output devices. As is known, groups or families of devices provided by specific manufacturers are often characterized in having processing or operational characteristics which are reduced to a set of fundamental primitive expressions that do not support the operations of other families of devices. In this case, more sophistication would be required in processing, increasing the complexity of the translation task and nullifying to a great extent the efficiencies that can be achieved with metafile expression storage.
Another disadvantage of metafile representation is that the original graph creation process, when operated to create a metafile, is unaware of the intended output device and thus cannot apply a procedure that optimizes the graphical layout to the output device characteristics. Translation of a device. independent metafile to a device-specific representation can result in a graph having an appearance of a lower quality than a graph designed with the attributes of the output device in mind. Such a process can be understood by reference to U.S. patent application No. 761,182, filed July 31, 1985 now U.S. Pat. No. 4,800,510, which is assigned to the assignee of the present invention, and which is incorporated herein by reference.
The process of adapting a graph to the characteristics of a specific output device requires the ability to modify the graph in non-geometric ways. This is possible only if the graph is described in very high level terms: the title, the axis scaling, and the legend annotation, for example, all need to be recognized as such to be modifiable in a graphically intelligent manner. The axis scale annotation, for example, cannot be modified intelligently if the text is known only as arbitrary text strings, as it would be in a metafile representation. This high level representation (source file) contains specifications such as graph type, graph data, annotation, etc. A source file is in effect an English language description of a graph, even though the actual format of the file may be more technical; it is often created by a human being and is most often human-readable. A straightforward translation of the human readable graph description into some high level internal data structure for use by a graph creation program in recreating the graph is referred to as a graph specification file. Although not all graph creation systems recognize the existence of this file, the "parsing" of user-entered specification usually creates this data structure at some point in a graph creation process. For the purposes of this description, graph specification files are considered equivalent to source files in terms of their capabilities of being processed.
It is also recognized that the creator of the graph may not be aware of the source file as a file. If the graph is created through an interactive command or natural language process, through a terminal screen oriented forms fill in system, or through an icon-based mouse driven system, the source file is not visible to the user. However, most systems provide for storage of the graph specification at a level equivalent to a source file, perhaps in the form of a graph specification file as discussed above and this representation is considered equivalent to source files in terms of their capabilities of being processed.
It should be evident that storage of graphs in the very high level representation corresponding to a source file offers great flexibility to a centralized graph creation system and permits intelligent handling of modifications to the graph. However, translation of a source file into a usable representation requires the provision of a substantial amount of sophisticated processing resources. Retrieval of a graph stored in source file representation for output on a specific device becomes equivalent to the creation of the graph, requiring a large amount of processing power and time. However, such high level representations are very compact for storage and require very little processing to create.
It will be appreciated from the preceding discussion that the problem of creating a graphical archive to serve the needs of many users requiring access to many graphs which are to be produced on a variety of output devices demands a flexible system permitting the storage of graphs in a variety of representational levels which can be retrieved quickly and efficiently. The provision for storage of a plurality of representational levels permits the system to be adapted to the specific functional needs of particular graph image applications, while the feature of rapid retrieval heightens the responsivity of the system to user needs.
Therefore, it is a primary objective of the subject invention to provide an archive system supporting the maintenance of graphs in a plurality of representations that reduces the system resources and operations required to store, retrieve, and produce a graph.